#include <iostream>
#include <vector>

using namespace std;

// 98.验证二叉搜索树
// 给定一棵二叉树，验证其是否为二分搜索树。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0),left(nullptr),right(nullptr) {}
    TreeNode(int x): val(x),left(nullptr),right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 中序遍历，判断是否为有序。只需判断当前结点和前序结点的关系即可。
class Solution {
private:
    int prev = INT_MIN;
public:
    bool isValidBST(TreeNode *root) {
        if(root == nullptr || (root->left == nullptr && root->right == nullptr))
            return true;

        return inorderTree(root);

    }
private:
    bool inorderTree(TreeNode *node) {
        if(node == nullptr)
            return true;

        if(!inorderTree(node->left))
            return false;
        // 处理根节点
        if(prev >= node->val)
            return false;
        // 更新前继节点的值
        prev = node->val;
        return inorderTree(node->right);

//        inorderTree(node->left);
//        if(node->val > prev) {
//            prev = node->val;
//        } else {
//            return false;
//        }
//        inorderTree(node->right);
    }
};

int main() {
    TreeNode* root = new TreeNode(2);

    TreeNode* left = new TreeNode(1);
    root->left = left;

    TreeNode* right = new TreeNode(3);
    root->right = right;
    //==============================
    auto *root2 = new TreeNode(5, new TreeNode(1),
                               new TreeNode(4,
                                            new TreeNode(3),
                                            new TreeNode(6)
                               )
    );
    TreeNode* root3 = new TreeNode(2, new TreeNode(2), new TreeNode(2));


    cout << Solution().isValidBST(root) << endl;    // true
    cout << Solution().isValidBST(root2) << endl;   // false
    cout << Solution().isValidBST(root3) << endl;   // false
    return 0;
}
